/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-26
 * Time: 13:38
 * @author 86189
 */
public class Solution2 {
    public static int InversePairs ( int [] array ) {
        //solution的解法中，首先是使用一个新数组，对原数组进行归并排序，然后放到新数组中，最后又要把排好序的数组赋值给原数组
        //那么其实我们可以直接在一开始就把原数组赋值给一个新的数组，在新数组上进行归并排序，
        // 在排序的过程中，直接把排好序的元素存储在原数组中，这样就较少了繁琐步骤
        //还有就是归并排序的划分和合并其实可以放在一个函数里面，因为划分和合并本来就是有先后顺序的
        //这一个函数即包含了划分的功能，也包含了合并排序的功能，划分完后就可以进行归并
        int[] tmp = new int [array.length];
        return merge(array,0,array.length-1,tmp);
    }
    
    private static int merge( int[] array, int left, int right,int[] tmp ) {
        if (left>=right) {
            //划分到两个区间各自只剩一个元素，是没有逆序对的
            return 0;
        }
        int mid = left + (right-left)/2;
        //这个时候还用不到新数组，所以新数组不需要改变
        int ret=merge(array,left,mid,tmp)+merge(array,mid+1,right,tmp);
        //直到各自元素只剩一个时。开始向上合并两个区间的数组
        ret%=1000000007;
        //i和j遍历新数组
        int i=left;
        int j=mid+1;
        //合并前先上一次合并好的原数组赋值给新数组,这样就保证了一部分已经有序
        for(int k=left;k<=right;k++){
            tmp[k]=array[k];
        }
        //k遍历原数组，这里是直接把排好序的元素放在原数组里面，
        // 这样不用像常规的归并排序的解法一样，先把排好序的放在新数组里面，
        // 后面又要把排好序的新数组赋值给原数组，这样比较繁琐
        //这里直接对新数组排序，排好序直接赋值给原数组
        for(int k=left;k<=right;k++){
            if(i==mid+1){
                //前半部分区间遍历完毕,直接把后半部分的元素复制给原数组
                array[k]=tmp[j++];
            }else if(j<=right && tmp[i]>tmp[j]){
                array[k]=tmp[j++];
                ret+=mid-i+1;
            }else{
                array[k]=tmp[i++];
            }
        }
        return ret%1000000007;
    }
    
    public static void main(String[] args) {
        int[] array={1,2,3,4,5,6,7,0};
        System.out.println(InversePairs(array));
    }
}
